import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;


public class Driver {
	public static void main(String [] args) {
//		BigInteger p = BigInteger.probablePrime(20, new Random());
//		BigInteger p = new BigInteger("2844244664798782226838734680773028322104996205763834045764978176142796814754573105472469136930751206077805102464353441610596921057314092815678475152733");
		BigInteger p = new BigInteger("91");
		System.out.println("p:\n" + p);
		
		//-----------------------------------
//		BigInteger a = new BigInteger(20, new Random());
//		BigInteger a = new BigInteger("2342677317138782040671615581476866093731121695750037418472568360600247136497636184505693086162175348945134903496251217828037042834235047307956823820967089");
//		BigInteger a = new BigInteger("1819418972928891961744405905337262042048749480738221638057344685753759605359869712475959703069094801593192108717637387717205213785735706475485879631807");
//		BigInteger a = new BigInteger("1819418972928891961744405905337262042048749480738221638057344685753759605359869712475959703069094801593192108717637387717205213785735706475485879631807");
		BigInteger a = new BigInteger("29");
		
		//-----------------------------------
//		BigInteger g = new BigInteger("5");
//		BigInteger g = new BigInteger("834402497135154950304863177519442137236737621012536327929814325381300066878336705672859366111476713879232979627765552500065091453711219740125246726907");
//		BigInteger g = new BigInteger("626433154266518851745577829549430534689442757394780252333327626455332946602556762505389427114366958130349842764902001393330136934457979272903797927468");
		BigInteger g = new BigInteger("63");
		
		System.out.println("g^s%p:\n" + raiseExponent(g, a, p));
		
//		Scanner scan = new Scanner(System.in);
//		System.out.println("B:");
//		BigInteger B = new BigInteger(scan.next());
//		System.out.println("B^a%p:\n" + raiseExponent(B, a, p));
	}
	
	//-------------------------------------------
	private static BigInteger raiseExponent(BigInteger g, BigInteger x, BigInteger p) {
		BigInteger result = new BigInteger("1");
		BigInteger power = new BigInteger(g.toByteArray());
		int bit = 0;
		while(bit < x.toByteArray().length * 8) {
			if(x.testBit(bit++)) {
				result = result.multiply(power);
			}
			power = power.multiply(power).mod(p);
		}
		return result.mod(p);
	}
}
